public class MyLinkList {

    static class Node {
        public int val;//数据域
        public Node next;//链表下一个节点的值

        Node(int val) {
            this.val = val;
        }
    }
        public Node head;//头节点
   //判断下标是否合法
    private  void checkIndex(int index) throws ListIndexOutOfException{
        if( index < 0 || index > size()){
            throw new ListIndexOutOfException("index位置不合法");
        }
    }
        //打印所有链表的值
        public void display(){
          Node cur = head;
          while ( cur != null){
              System.out.print(cur.val+" ");
              cur = cur.next;
          }
            System.out.println();

        }

        //头插法 O(1)
        public void addFirst(int data){
            Node node = new Node(data);

            if(head == null){//如果是头节点为空，直接把地址夫给头节点
                head = node;
            }else{
                node.next = head;
                head = node;
            }
        }


        //尾插法 O(1)
        public void addLast(int data) {
           Node node = new Node(data);
           Node cur = head;
           if(cur == null){
               addFirst(data);
           }else{
               while (cur.next != null){
                   cur = cur.next;
               }
                cur.next = node;
           }


        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data) throws ListIndexOutOfException{
            checkIndex(index-1);
            if(index-1 == 0){
                addFirst(data);
                return;
            }
            if (index-1 == size()){
                addLast(data);
                return;
            }

            Node node = new Node(data);
            Node cur = head;
            int count = 0;
            while (count < index-2){
                cur = cur.next;
                index--;
            }
            node.next = cur.next;
            cur.next = node;

        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){

            if(judgeListIsNull(head)){
                return false;
            }
            Node cur = head;
            while (cur != null){
                if(cur.val == key){
                    return true;
                }else{
                    cur = cur.next;
                }
            }
          return false;
        }

        //删除第一次出现关键字为key的节点
        public void remove(int key){
          if(judgeListIsNull(head)){
              return ;
          }

          Node cur = head;
          if(cur.val == key){
              head = head.next;
              return;
          }
          while (cur != null){
              if(cur.next.val == key){
                  cur.next = cur.next.next;
                  return;
              }else {
                  cur = cur.next;
              }
          }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
            if(judgeListIsNull(head)){
                return;
            }
            Node cur = head.next;
            Node prev = head;
            while(cur != null){
                if(cur.val == key){
                    prev.next = cur.next;
                }else{
                    prev = cur;
                }
                cur = cur.next;
            }
               if(head.val == key){
                   head =head.next;
               }
        }
        //链表的长度
        public int size(){
            int count = 0;
            Node cur = head;
            while (cur != null){
                count++;
                cur = cur.next;
            }
            return count;
        }

        //回收链表
        public void clear(){
            head = null;

        }

        //判断链表是否为空
     public boolean judgeListIsNull(Node node) {
            if(node == null){
                return true;
            }else{
                return false;
            }
    }


}


